package com.sheng.leetcode.year2023.month09.day07;

import org.junit.Test;

/**
 * @author by ls
 * @date 2023/9/7
 * <p>
 * 2594. 修车的最少时间<p>
 * <p>
 * 给你一个整数数组 ranks ，表示一些机械工的 能力值 。ranksi 是第 i 位机械工的能力值。<p>
 * 能力值为 r 的机械工可以在 r * n^2 分钟内修好 n 辆车。<p>
 * 同时给你一个整数 cars ，表示总共需要修理的汽车数目。<p>
 * 请你返回修理所有汽车 最少 需要多少时间。<p>
 * 注意：所有机械工可以同时修理汽车。<p>
 * <p>
 * 示例 1：<p>
 * 输入：ranks = [4,2,3,1], cars = 10<p>
 * 输出：16<p>
 * 解释：<p>
 * - 第一位机械工修 2 辆车，需要 4 * 2 * 2 = 16 分钟。<p>
 * - 第二位机械工修 2 辆车，需要 2 * 2 * 2 = 8 分钟。<p>
 * - 第三位机械工修 2 辆车，需要 3 * 2 * 2 = 12 分钟。<p>
 * - 第四位机械工修 4 辆车，需要 1 * 4 * 4 = 16 分钟。<p>
 * 16 分钟是修理完所有车需要的最少时间。<p>
 * <p>
 * 示例 2：<p>
 * 输入：ranks = [5,1,8], cars = 6<p>
 * 输出：16<p>
 * 解释：<p>
 * - 第一位机械工修 1 辆车，需要 5 * 1 * 1 = 5 分钟。<p>
 * - 第二位机械工修 4 辆车，需要 1 * 4 * 4 = 16 分钟。<p>
 * - 第三位机械工修 1 辆车，需要 8 * 1 * 1 = 8 分钟。<p>
 * 16 分钟时修理完所有车需要的最少时间。<p>
 * <p>
 * 提示：<p>
 * 1 <= ranks.length <= 10^5<p>
 * 1 <= ranks[i] <= 100<p>
 * 1 <= cars <= 10^6<p>
 */
public class LeetCode2594 {

    @Test
    public void test01() {
//        int[] ranks = {4, 2, 3, 1};
//        int cars = 10;
        int[] ranks = {5, 1, 8};
        int cars = 6;
        System.out.println(new Solution().repairCars(ranks, cars));
        System.out.println(Math.sqrt(4 / 3));
    }
}

class Solution {

    public long repairCars(int[] ranks, int cars) {
        // 能力值为 r 可以在 r * n^2 内修好 n 辆车
        // 修理工能力差值为 4 倍的时候，相同时间内修好的汽车数量为 2 倍
        // 假设修理工 A 的能力值 为 a，修理工 B 的能力值为 b，那么有以下等式 a / b == 4 时，存在 a * n^2 == b * 4n^2
        // 假设一个是 1，一个是 3，那么能力值为 1 的学生修好 2 辆车的时间内，能力值为 3 的学生能修好 sqrt(4 / 3) 辆车，即为 sqrt(时间 / 能力值)
        long left = 0, right = Long.MAX_VALUE;
        while (left < right) {
            long mid = (left + right) >> 1;
            if (cal(ranks, cars, mid)) {
                // 修理的车辆数目超过预期代表时间过多
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }

    public boolean cal(int[] ranks, int cars, long mid) {
        long sum = 0;
        // 获取时间 mid内所能修理的车辆数目
        for (int rank : ranks) {
            sum += (long) Math.sqrt(mid / rank);
        }
        return sum >= cars;
    }
}
